package insertionsort;

import common.CreateTestArrUtils;

import java.util.Arrays;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/8/13 2:23
 * 直接插入排序
 * 平均时间复杂度 O(n^2)
 */
public class InsertionSort {

    /**
     * 直接插入排序
     */
    public static void insertionSort(int[] arr) {
        if (arr == null) {
            throw new NullPointerException();
        }
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i]; // 待插入的值
            int j = i - 1;
            while (j >= 0) {
                if (arr[j] > temp) {
                    // 后移
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
                j--;
            }
            // 插入
            arr[j + 1] = temp;
        }
    }

    public static void main(String[] args) {
        int[] descArr = CreateTestArrUtils.createDescArr(100);
        System.out.println("原数组 arr=" + Arrays.toString(descArr));
        insertionSort(descArr);
        System.out.println("排序后数组 arr=" + Arrays.toString(descArr));
    }
}
